package com.example.algorithm.backtrcaking;

import java.util.ArrayList;
import java.util.List;

/**
 * @author : zhy
 * @since : 2022/8/10
 * 组合
 */
public class Combination {

    public List<List<Integer>> combine(int n, int k) {
        List<Integer> list = new ArrayList<>();
        List<List<Integer>> listList = new ArrayList<>();

        backTrack(list,listList,n,k,1);
        return listList;
    }

    private void backTrack(List<Integer> list, List<List<Integer>> listList, int n, int k,int start) {
                if(list.size()==k){
                    listList.add(new ArrayList<>(list));
                    return;
                }
                for(int i=start;i<=n-(k-list.size())+1;i++){
                    list.add(i);
                    backTrack(list, listList, n, k, i+1);
                    list.remove(list.size()-1);
                }
    }

    public static void main(String[] args) {
        Combination combination = new Combination();
        List<List<Integer>> combine = combination.combine(4, 2);
        System.out.println(combine);
    }
}
